package com.ljy.my_study.lintcode.最大子数组III;
/** 
* @author James
* @date 2019年2月2日 
*/
public class TestMain {
//	给定一个整数数组和一个整数 k，找出 k 个不重叠子数组使得它们的和最大。每个子数组的数字在数组中的位置应该是连续的。
//
//	返回最大的和。
//
//	样例
//	给出数组 [-1,4,-2,3,-2,3] 以及 k = 2，返回 8
//
//	注意事项
//	子数组最少包含一个数
	
//	Example
//	Given [-1,4,-2,3,-2,3], k=2, return 8
//
//	分析：与Best Time to Buy and Sell Stock IV类似，两个数组分别记录包含当前值的本地最优解和全局最优解。local[i][j]代表从0到nums中第i个数字处，分成j个数组后，和的最大值,且必须包括第i个数字，这样可以排除第i个数组包含在前一个数组中的情况。global[i][j]代表从0到nums第i个数字处，分成j个数组后和的最大值。
//	二维数组动态规划的状态转移方程为：
//
//	local[i][j] = Math.max(local[i - 1][j], global[i - 1][j - 1])  + nums[i - 1];
//
//	global[i][j] = Math.max(global[i - 1][j], local[i][j]);
	public static void main(String[] args) {
//		System.out.println(maxSubArray(new int[] {1,2,-1,3},));
	}
	
	public static int maxSubArray(int[] nums, int k) {
		int numsLen=nums.length;
		if(k>numsLen) return 0;
		int[][] local=new int[numsLen+1][k+1];
		int[][] global=new int[numsLen+1][k+1];
		for(int i=1;i<=numsLen;i++) {
			local[i][0]=Integer.MIN_VALUE;
			for(int j=1;j<=k;j++) {
				if(j>i) {
					local[i][j]=global[i][j]=Integer.MIN_VALUE;
					continue;
				}
				local[i][j]=Math.max(local[i-1][j],global[i-1][j-1])+nums[i-1];
				if(i==j) {
					global[i][j]=local[i][j];
				}else {
					global[i][j] = Math.max(global[i - 1][j], local[i][j]);
				}
			}
		}
		return global[numsLen][k];
	}
}
